package com.lishem.carl._10dp;

import java.util.Scanner;

/**
 * https://kamacoder.com/problempage.php?pid=1052
 * <p>
 * 小明是一位科学家，他需要参加一场重要的国际科学大会，以展示自己的最新研究成果。
 * <p>
 * 他需要带一些研究材料，但是他的行李箱空间有限。这些研究材料包括实验设备、文献资料和实验样本等等，
 * <p>
 * 它们各自占据不同的重量，并且具有不同的价值。
 * <p>
 * * 小明的行李箱所能承担的总重量为 N，问小明应该如何抉择，才能携带最大价值的研究材料，
 * <p>
 * 每种研究材料可以选择无数次，并且可以重复选择。
 */
public class _13KaMaCode_完全背包 {


    /**
     * @param N       材料种类
     * @param V       行李空间 （背包）
     * @param weights 第i种材料重量
     * @param values  第i种材料价值
     * @return
     */
    private static int getMaxWeight(int N, int V, int[] weights, int[] values) {
        int[][] dp = new int[N][V + 1];
        // dp[i][j]代表从0-i个物品中任选，使容量为j的背包能装的最大价值
        for (int i = 0; i < dp[0].length; i++) {
            if (weights[0] < i) {
                int z = i / weights[0];
                dp[0][i] = z * values[0];
            }
        }

        for (int i = 1; i < dp.length; i++) {
            for (int j = 0; j < dp[0].length; j++) {
                if (j - weights[i] >= 0) {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - weights[i]] + values[i]);
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }

        return dp[dp.length - 1][V];
    }


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int V = sc.nextInt();
        int[] weights = new int[N];
        int[] values = new int[N];
        for (int i = 0; i < N; i++) {
            weights[i] = sc.nextInt();
            values[i] = sc.nextInt();
        }
        int res = getMaxWeight(N, V, weights, values);
        System.out.println(res);
    }
}
